#include <vector>
#include <string>
using namespace std;


//version 1
class Solution {
public:
//采用相对映射
    vector<int> findAnagrams(string s, string p) {
        vector<int> s_hash(26, 0), p_hash(26, 0), ret;

        //先统计p_hash中的情况
        for(auto& ch : p)
            p_hash[ch - 'a']++;
        
        for(int left = 0, right = 0; right < s.size(); ++right){
            //1.入窗口(进入到s_hash)
            s_hash[s[right] - 'a']++;

            if(right - left + 1 == p.size()){
                if(s_hash == p_hash)
                    ret.push_back(left);
                
                s_hash[s[left] - 'a']--;
                ++left;
            }
        }

        return ret;
    }
};


// version 2
class Solution {
public:
//采用相对映射 
//针对于题目中出现的会有不存在的字符，我们可以考虑优化一下
    vector<int> findAnagrams(string s, string p) {
        vector<int> s_hash(26, 0), p_hash(26, 0), ret;

        //先统计p_hash中的情况
        for(auto& ch : p)
            p_hash[ch - 'a']++;
        
        for(int left = 0, right = 0; right < s.size(); ++right){
            //1.入窗口(进入到s_hash)
            char input = s[right];
            if(p_hash[input - 'a'] == 0){
                //这个是不存在于p中的，没必要往后继续判断了
                left = right + 1;
                //清空s_hash
                for(auto& x : s_hash) x = 0;
                continue;
            }
            s_hash[input - 'a']++;

            if(right - left + 1 == p.size()){
                if(s_hash == p_hash)
                    ret.push_back(left);
                
                s_hash[s[left] - 'a']--;
                ++left;
            }
        }

        return ret;
    }
};


//version 3
class Solution {
public:
//采用相对映射 
//针对于题目中出现的会有不存在的字符，我们可以考虑优化一下
//为了应对更复杂的情况，对于两个哈希表是否相等我们来进行进一步优化 （统计有效字符个数即可）
    vector<int> findAnagrams(string s, string p) {
        vector<int> s_hash(26, 0), p_hash(26, 0), ret;
        int useful_ch_num = 0;

        //先统计p_hash中的情况
        for(auto& ch : p)
            p_hash[ch - 'a']++;
        
        for(int left = 0, right = 0; right < s.size(); ++right){
            //1.入窗口(进入到s_hash)
            char input = s[right];
            if(p_hash[input - 'a'] == 0){
                //这个是不存在于p中的，没必要往后继续判断了
                left = right + 1;
                //清空s_hash
                for(auto& x : s_hash) x = 0;
                //窗口内有效字符个数清空
                useful_ch_num = 0;
                continue;
            }

            //这个字符是存在的 -> 判断是否有效 -> 再来入窗口(因为判断是否有效是要在入窗口的时候来做)
            if(s_hash[input - 'a'] < p_hash[input - 'a']) ++useful_ch_num;
            s_hash[input - 'a']++;

            if(right - left + 1 == p.size()){
                if(useful_ch_num == p.size())
                    ret.push_back(left);
                
                //出窗口前，就得判断是否需要调整有效字符个数
                char output = s[left];
                if(s_hash[output - 'a'] <= p_hash[output - 'a']) --useful_ch_num;
                
                //出窗口
                s_hash[s[left] - 'a']--;
                ++left;
            }
        }

        return ret;
    }
};